/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._206;

import java.util.LinkedList;

/**
 *
 * 反转一个单链表。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._206
 * @ClassName: ReverseLinkedList
 * @Author: linyaonan
 * @Date: 2019/12/10 15:35
 */
public class ReverseLinkedList {

    public ListNode re1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        LinkedList<Integer> list = new LinkedList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        ListNode h = new ListNode(-1);
        ListNode r = h;
        while (!list.isEmpty()) {
            Integer i = list.removeLast();
            h.next = new ListNode(i);
            h= h.next;
        }
        return r.next;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode h = null;
        while(head != null) {
            ListNode child = new ListNode(head.val);
            child.next = h;
            head = head.next;
            h = child;
        }
        return h;
    }

    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = null;
        ListNode c = head;
        while(c != null) {
            ListNode temp = c.next;
            c.next = p;
            p = c;
            c = temp;
        }
        return p;
    }

    /**
     * 原地翻转链表
     * 假设在0-k位置已经翻转完成，那么只需要将0-k作为整体，翻转与k的位置
     * pre,k,后续数据，翻转pre,k的关系时需要将后续数据先保存起来
     *
     * k.next = pre
     *
     *
     * @param head
     * @return
     */
    public ListNode r4(ListNode head) {
        // 1. 特殊情况判断
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        ListNode pre = null;

        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }

        return pre;
    }

    public ListNode re3(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode c = head;
        ListNode p = null;
        while (c != null) {
            ListNode t = c.next;
            c.next = p;
            p = c;
            c = t;
        }

        return p;
    }

}
